Recursion
Base case & general case
- Recursion is a process using a function or procedure that is defined in terms of itself and calls itself.
- The process is defined using a base case, a terminating solution to a process that is not recursive, and a general case, a solution to a process that is recursively defined.
py
def factorial(n):
if n= 1:
return 1 #base case
return n * factorial(n-1) #general case
n = int(input())
result = factorial(n)
print(result)
Winding & unwinding
- With recursive functions, the statements after the recursive function call are not executed until the base case is reached; this is called winding.
- After the base case is reached and can be used in the recursive process, the function is unwinding.
Benefits of recursion
- Recursive solutions can contain fewer programming statements than an iterative solution.
- The solutions can solve complex problems in a simpler way than an iterative solution.
- However, if recursive calls to procedures and functions are very repetitive, there is a very heavy use of the stack, which can lead to stack overflow.
- For example, factorial(100) would require 100 function calls to be placed on the stack before the function unwinds.
How a compiler implements recursion
- Recursive code needs to make use of the stack; therefore, in order to implement recursive procedures and functions in a high-level programming language, a compiler must produce object code that pushes return addresses and values of local variables onto the stack with each recursive call, winding.
- The object code then pops the return addresses and values of local variables off the stack, unwinding.
py
def fib(n):
if n <= 2:
return 1 #base case
return fib(n-1) + fib(n-2) #general case